Теорема о числе сюрьекций

Пусть $B$ и $C$ — множества, $|B| = n, |C| = k$. Существует $k^n$ различных функций из $B$ в $C$, так как есть $k$ способов выбрать образ для каждого из $n$ элементов.

Число сюрьекций $n$-элементного множества $B$ на $k$-элементное множество $C$ равно $$sur(n, k) = \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n.$$

Пусть $A = \{f \mathpunct{:} B \to C\}$, $C = \{c_1, \dots, c_k\}$. Возьмём следующие свойства $P_1, \dots, P_k$ для элементов $A$: $$P_i = \text{«образ функции не содержит элемента } c_i\text{»}$$ Тогда $|A_i| = (k-1)^n$ для любого $i$. Более того, для любого $X \subset \{1, \dots, k\}$, $|\bigcap_{i \in X} A_i| = (k - |X|)^n$. Можно воспользоваться симметричной формулой включений-исключений, где размер пересечения $j$ множеств свойств равен $(k-j)^n$. Следовательно, $$sur(n, k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n = \sum_{j=0}^{k} (-1)^j \binom{k}{k-j} (k-j)^n = \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$$ $\square$